Arrow Research search

Author name cluster

Bruno Guillon

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers
1 author row

Possible papers

7

I&C Journal 2023 Journal Article

Weight-reducing Turing machines

  • Bruno Guillon
  • Giovanni Pighizzini
  • Luca Prigioniero
  • Daniel Průša

It is well known that one-tape Turing machines running in linear time are no more powerful than finite automata; namely they recognize exactly the class of regular languages. We prove that it is not decidable if a one-tape machine runs in linear time, even if it is deterministic and restricted to use only the portion of the tape that initially contains the input. This motivates the introduction of a constructive variant of one-tape machines, called a weight-reducing machine, and the investigation of its properties. We focus on the deterministic case. In particular, we show that, paying a polynomial size increase only, each weight-reducing machine can be turned into a halting one that runs in linear time. Furthermore each weight-reducing machine can be converted into equivalent nondeterministic and deterministic finite automata by paying an exponential and doubly-exponential increase in size, respectively. These costs cannot be reduced in the worst case.

Details DOI

I&C Journal 2022 Journal Article

Converting nondeterministic two-way automata into small deterministic linear-time machines

  • Bruno Guillon
  • Giovanni Pighizzini
  • Luca Prigioniero
  • Daniel Průša

In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and one-way nondeterministic automata into equivalent two-way deterministic automata. Despite all the attempts, the question has been answered only for particular cases, while it remains open in general, the best upper bound currently known being exponential. We present a new approach in which unrestricted nondeterministic automata are simulated by deterministic models extending two-way deterministic automata, paying only a polynomial increase of size. Indeed, we study the costs of the conversions of nondeterministic automata into some variants of one-tape deterministic Turing machines working in linear time; namely Hennie machines, weight-reducing Turing machines, and weight-reducing Hennie machines. All these variants are known to share the same computational power: they characterize the class of regular languages.

Details DOI

I&C Journal 2021 Journal Article

Reversible pushdown transducers

  • Bruno Guillon
  • Martin Kutrib
  • Andreas Malcher
  • Luca Prigioniero

Deterministic pushdown transducers are studied with respect to their ability to compute reversible transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are also backward deterministic and thus are able to uniquely step the computation back and forth. The families of transductions computed are classified with regard to four types of length-preserving transductions as well as to the property of working reversibly. It turns out that accurate to one case separating witness transductions can be provided. For the remaining case it is possible to establish the equivalence of both families by proving that stationary moves can always be removed in length-preserving reversible pushdown transductions.

Details DOI

TCS Journal 2019 Journal Article

Linear-time limited automata

  • Bruno Guillon
  • Luca Prigioniero

The time complexity of 1-limited automata is investigated from a descriptional complexity view point. Though the model recognizes regular languages only, it may use quadratic time in the input length. We show that, with a polynomial increase in size and preserving determinism, each 1-limited automaton can be transformed into a linear-time equivalent one. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines (i. e. , one-tape Turing machines syntactically forced to operate in linear-time), and we show exponential gaps for the converse transformations in the deterministic case.

Details DOI

Highlights Conference 2018 Conference Abstract

Determinizing two-way automata with linear-time Turing machines

  • Bruno Guillon

ABSTRACT. In 1968, Sakoda and Sipser conjectured that the simulation cost of the determinization of two-way automata is exponential in the worst case. In spite of all attempts the problem remains open today. In this work we propose a new approach, in which the simulating deterministic machine has further abilities besides the read-only capacity of two-way automata. We prove a polynomial size-cost simulation of two-way nondeterministic automata by deterministic weight-reducing Turing machines, a syntactical restriction of linear-time Turing machines which recognize regular languages only, as proved by Hennie in 1965. We then discuss the cost of the conversion into weight-reducing linear-bounded-automata, which constrain the former model by restricting the space to the portion of the tape that initially contain the input word. This is a joint work with Giovanni Pighizzini, Luca Prigioniero and Daniel Průša that has been presented at DLT'18.

Details

I&C Journal 2014 Journal Article

Two-way automata making choices only at the endmarkers

  • Viliam Geffert
  • Bruno Guillon
  • Giovanni Pighizzini

The question of the state-size cost for simulation of two-way nondeterministic automata (2 nfas) by two-way deterministic automata (2 dfas) was raised in 1978 and, despite many attempts, it is still open. Subsequently, the problem was attacked by restricting the power of 2 dfas (e. g. , using a restricted input head movement) to the degree for which it was already possible to derive some exponential gaps between the weaker model and the standard 2 nfas. Here we use an opposite approach, increasing the power of 2 dfas to the degree for which it is still possible to obtain a subexponential conversion from the stronger model to the standard 2 dfas. In particular, it turns out that subexponential conversion is possible for two-way automata that make nondeterministic choices only when the input head scans one of the input tape endmarkers. However, there is no restriction on the input head movement. This implies that an exponential gap between 2 nfas and 2 dfas can be obtained only for unrestricted 2 nfas using capabilities beyond the proposed new model. As an additional bonus, conversion into a machine for the complement of the original language is polynomial in this model. The same holds for making such machines self-verifying, halting, or unambiguous. Finally, any superpolynomial lower bound for the simulation of such machines by standard 2 dfas would imply L ≠ NL. In the same way, the alternating version of these machines is related to L =? NL =? P, the classical computational complexity problems.

Details DOI
v2026.09.13