nach oben

Theory of Computing Systems

Erschienen in:

01.05.2015

Two-Way Automata Characterizations of L/poly Versus NL

verfasst von: Christos A. Kapoutsis, Giovanni Pighizzini

Erschienen in: Theory of Computing Systems | Ausgabe 4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Let L/p o l y and N L be the standard complexity classes, of languages recognizable in logarithmic space by Turing machines which are deterministic with polynomially-long advice and nondeterministic without advice, respectively. We recast the question whether \(\mathsf {L}/\mathsf {poly}~{\supseteq }~{\mathsf {NL}}\) in terms of deterministic and nondeterministic two-way finite automata (2dfas and 2nfas). We prove it equivalent to the question whether every s-state unary 2nfa has an equivalent poly(s)-state 2dfa, or whether a poly(h)-state 2dfa can check accessibility in h-vertex graphs (even under unary encoding) or check two-way liveness in h-tall, h-column graphs. This complements two recent improvements of an old theorem of Berman and Lingas. On the way, we introduce new types of reductions between regular languages (even unary ones), use them to prove the completeness of specific languages for two-way nondeterministic polynomial size, and propose a purely combinatorial conjecturethat implies \(\mathsf {L}/\mathsf {poly}~{\nsupseteq }~\mathsf {NL}\).

Vorheriger Artikel On Extracting Space-bounded Kolmogorov Complexity

Nächster Artikel Omega-Rational Expressions with Bounded Synchronization Delay

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

It is tempting to consider the following, simpler simulation. From (q,i) on \({\vdash }\), \(M^{\prime }\) sweeps the tape deterministically up to cell i (using states of the form (q,i,j) with j<i), where it records x _i in its memory; it then completes the sweep in state (q,i,x _i), jumping back to \({\vdash }\) in that same state. From there, it transitions nondeterministically to states of the form (p,i±1) according to the choices of M from q on x _i. This can be implemented with O(s l ²+s l σ) states, where σ=|Σ|. If σ is constant in s, then this is O(s l ²) states, better than in Lemma 1. If σ=poly(s), then it increases to poly(s)⋅l ² states, still good for Corollary 1. But if σ is super-polynomial in s, then the size of \(M^{\prime }\) becomes super-polynomial as well, and Corollary 1 cannot follow.

As suggested by a reviewer, if we require that \(M^{\prime }\) agrees with M only on inputs of length exactly l, then the simulation can be improved reducing to O(s ² l) the number of states of \(M^{\prime }\). This can be done as follows. The event of M being in state q and on tape cell i is directly simulated by \(M^{\prime }\) in the same state q on the same tape cell i. From this configuration, using a counter bounded by l, \(M^{\prime }\) can ‘rotate’ along the input to reach again cell i. During this phase, when \(M^{\prime }\) reaches \({\vdash }\), it makes a nondeterministic ‘guess’ of a pair (p,d)∈S×{L,R}, and when it finally reaches cell i, \(M^{\prime }\) verifies that the guess corresponds to a valid transition of M. If this is the case, then \(M^{\prime }\) moves to cell i+d (in the case d=−1 this is done again using a rotation and a counter), otherwise it hangs.

Actually the construction in [3] assumes acceptance on \({\vdash }\) in \(\tilde {q}_{f}\). Furthermore, \(\tilde {q}_{f}\) can be entered only from some states in \(\tilde {S}_{B}\) on \({\vdash }\), without moving the input head. To be consistent with the acceptance condition given in Section 2.1, we make the following minor changes to \(\tilde {M}\), which do not affect the set of states. Each transition entering \(\tilde {q}_{f}\) on \({\vdash }\) moves the head to the right. Furthermore, in the state \(\tilde {q}_{f}~\tilde {M}\) always moves to the right, without changing state. This is done even on ⊣. In this way, once \(\tilde {q}_{f}\) is entered, \(\tilde {M}\) completely scans the input by remaining in \(\tilde {q}_{f}\), in order to accept after violating ⊣.

We remind the reader that, since \(\tilde {M}\) is a sofa, the direction of the head in its transitions is implicit, i.e, the set of transitions is a subset of \(\tilde {S}\times ({\varSigma }\cup \{{\vdash }{,}{\dashv }\})\times \tilde {S}\).

Notice that \(\tilde {M}\) has the transition \((q_{\mathrm {f}},{\dashv },\tilde {q}_{\mathrm {f}})\) (cf. note 3). Hence, q≠q _f here.

The two-way liveness problem is classically defined using two-column graphs as alphabet symbols. As pointed out by a reviewer, we could use a modified version of this problem, where each alphabet symbol is defined by just one column with outgoing edges, to the left and to the right, that reach, when symbols are concatenated, vertices in the adjacent symbols. Let \(\text {TWL}^{\prime }_{h}\) be the problem so modified for graphs of height h. Then in the statement of Lemma 5 we can write \(\mathfrak {L}\leq _{\text {h}}\text {TWL}^{\prime }_{s}\).

Notice that even in this case, the string produced by T in a printing step (which contains one or more infixes #z _i) does not need to be explicitly represented: it only depends on the simulated printing step of T.

When a printing step of T produces an infix #z _i#z _i+1⋯#z _k, M ₁ can compute in a single step \(\bigl (\bigl (\cdots \bigl ((\rho \cdot n_{i} \bmod l_{j} ) \cdot n_{i+1} \bigr ) \bmod l_{j} \cdots \bigr ) \cdot n_{k} \bigr ) \bmod l_{j} \,. \) Since the infix depends only on the printing step of T, this can be embedded in the transition function of M ₁, without explicitly representing the infix #z _i#z _i+1⋯#z _k.

Fix any bijection π from the binary relations on [h] to the numbers in \([2^{h^{2}}]\). Then the homomorphic image f(A,L) of a left symbol (A,L) is the partial function that only maps the number π(A) to itself. The image f(B,R) of a right symbol (B,R) is the partial function in which a number i can only map to itself, and this holds iff i=π(A) for some A that matches with B. Clearly then, A,B match iff f(A,L),f(B,R) match (by the one two-step cycle going from π(A) on the left column to π(A) on the right column and back).

Berman, P., Lingas, A.: On complexity of regular languages in terms of finite automata. Report 304, Institute of Computer Science, Polish Academy of Sciences, Warsaw (1977)

Geffert, V., Guillon, B., Pighizzini, G.: Two-way automata making choices only at the endmarkers, Inf. Comput. doi:10.1016/j.ic.2014.08.009 (2014)

Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theor. Comput. Sci. 295, 189–203 (2003)CrossRefMATHMathSciNet

Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Inf. Comput. 205 (8), 1173–1187 (2007)CrossRefMATHMathSciNet

Geffert, V., Pighizzini, G.: Two-way unary automata versus logarithmic space. Inf. Comput. 209 (7), 1016–1025 (2011)CrossRefMATHMathSciNet

Hardy, G.H., Wright, E.M.: An introduction to the theory of numbers. Oxford Science Publications (1979)

Kapoutsis, C.: Size complexity of two-way finite automata. In: Proceedings of DLT, pp. 47–66 (2009)

Kapoutsis, C.: Two-way automata versus logarithmic space. Theory Comput. Syst. 55(2):421–447 (2014)

Kunc, M., Okhotin, A.: Describing periodicity in two-way deterministic finite automata using transformation semigroups. In: Proceedings of DLT, pp. 324–336 (2011)

10.

Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of STOC, pp. 275–286 (1978)

11.

Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4, 177–192 (1970)CrossRefMATHMathSciNet

Titel: Two-Way Automata Characterizations of L/poly Versus NL
verfasst von: Christos A. Kapoutsis
Giovanni Pighizzini
Publikationsdatum: 01.05.2015
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2015
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-014-9560-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2015

Towards Optimal Degree Distributions for Left-Perfect Matchings in Random Bipartite Graphs

New Lower Bounds on Circuit Size of Multi-output Functions

Generalized Post Embedding Problems

Omega-Rational Expressions with Bounded Synchronization Delay

Some Results on More Flexible Versions of Graph Motif

Preface

Premium Partner