Abstract
Closure underlength-preserving homomorphisms is interesting because of its similarity tonondeterminism. We give a characterization of NP in terms of length-preserving homomorphisms and present related complexity results. However, we mostly study the case of two-way finite automata: Let l.p.hom[n state 2DFA] denote the class of languages that are length-preserving homomorphic images of languages recognized byn-state 2DFAs. We give a machine characterization of this class. We show that any language accepted by ann-state two-wayalternating finite automaton (2AFA), or by a l-pebble 2NFA, belongs to l.p.hom[O(n 2) state 2DFA]. Moreover, there are languages in l.p.hom[n state 2DFA] whose smallest accepting 2NFA has at leastc n states (for some constantc > 1). So for two-way finite automata, the closure under length-preserving homomorphisms is much more powerful than nondeterminism. We disprove two conjectures (of Meyer and Fischer, and of Chrobak) about the state-complexity of unary languages. Finally, we show that the equivalence problems for 2AFAs (resp. 1-pebble 2NFAs) are in PSPACE, and that the equivalence problem for 1-pebble 2AFAs is in ExpSPACE (thus answering a question of Jiang and Ravikumar); it was known that these problems are hard in these two classes. We also give a new proof that alternating 1-pebble machines recognize only regular languages (which was first proved by Goralčíket al.).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
T. Apostol,Introduction to Analytic Number Theory, Springer-Verlag, New York, 1976.
A. Aho, J. Hopcroft, and J. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.
J.-C. Birget, Concatenation of inputs in a two-way automaton,Theoretical Computer Science 63 (1989), 141–156.
J.-C. Birget, Basic techniques for two-way finite automata, in: J. E. Pin (ed.),Formal Properties of Finite Automata and Applications, Lecture Notes in Computer Science, Vol. 386, Springer-Verlag, Berlin, 1989, pp. 56–64.
J.-C. Birget, Positional simulation of two-way automata: proof of a conjecture of R. Kannan, and generalizations,Journal of Computer and System Sciences 45 (1992), 154–179 (special issue onSTOC 89).
J.-C. Birget, State-complexity of finite-state devices, state-compressibility and incompressibility,Mathematical Systems Theory 26 (1993), 237–269.
J.-C. Birget, Partial orders on words, minimal elements in regular languages, and state complexity,Theoretical Computer Science,119 (1993), 267–291.
J.-C. Birget, The minimum automaton for certain languages, in preparation.
R. Book and S. Greibach, Quasi-realtime languages,Mathematical Systems Theory 4 (1970), 97–111.
M. Blum and C. Hewitt, Automata on a 2-dimensional tape,Proceedings of the 8th IEEE Symposium on Switching and Automata Theory, 1965, pp. 155–160.
D. A. M. Barrington, K. Compton, H. Straubing, and D. Thérien, Regular languages in NC1,Journal of Computer and System Sciences, to appear.
J. Brzozowski and E. Leiss, On equations for regular languages, finite automata, and sequential networks,Theoretical Computer Science 10 (1980), 19–35.
D. A. M. Barrington and D. Thérien, Finite monoids and the fine structure of NC1,Journal of the Association for Computing Machinery 35 (1988), 941–952.
M. Chrobak, Finite automata and unary languages,Theoretical Computer Science 47 (1986), 149–158.
A. Chandra, D. Kozen, and L. Stockmeyer, Alternation,Journal of the Association for Computing Machinery 28 (1981), 114–133.
S. Cook, A taxonomy of problems with fast parallel algorithms,Information and Control 64 (1985), 2–22.
A. Chandra and L. Stockmeyer, Alternation,Proceedings of the 17thIEEE Annual Symposium on Foundations of Computer Science, 1976, pp. 98–108.
P. Denning, J. Dennis, and J. Qualitz,Machines, Languages, and Computation, Prentice-Hall, Englewood Cliffs, NJ, 1978.
P. Goralčík, A. Goralčíková, and V. Koubek, Alternation with a pebble,Information Processing Letters 38 (1991), 7–13.
F. C. Hennie, One-tape off-line Turing machine computations,Information and Control 8 (1965), 553–578.
H. B. Hunt III, On the time and tape complexity of languages, I,Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 1973, pp. 10–19.
J. Hopcroft and J. Ullman,Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979.
O. Ibarra and B. Ravikumar: Sublogarithmic-space Turing machines, nonuniform space complexity, and closure properties,Mathematical Systems Theory 21 (1988), 1–17.
O. Ibarra and S. Sahni, Hierarchies of Turing machines with restricted tape alphabet size,Journal of Computer and System Sciences 11 (1975), 56–67.
T. Jiang and B. Ravikumar, A Note on the Space Complexity of Some Decision Problems for Finite Automata,Information Processing Letters 40 (1991), 25–31.
R. Kannan, Alternation and the power of non-determinism,Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 344–346.
D. Kozen, On parallelism in Turing machines,Proceedings of the 17th IEEE Annual Symposium on Foundations of Computer Science, 1976, pp. 89–97.
E. Leiss, Succinct representation of regular languages by boolean automata,Theoretical Computer Science 13 (1981), 323–330.
E. Leiss, Succinct representation of regular languages by boolean automata, II,Theoretical Computer Science 38 (1985), 133–136.
R. Ladner, R. Lipton, and L. Stockmeyer, Alternating pushdown automata,Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, 1978, pp. 92–106, andSIAM Journal of Computing,13(1) (1984), 135–155.
P. M. Lewis, R. Stearns, and J. Hartmanis, Memory bounds for recognition of context-free and context-sensitive languages,Proceedings of the 6th IEEE Symposium on Switching Circuit Theory and Logical Design, 1965, pp. 191–202.
P. Michel, An NP-complete language accepted in linear time by a one-tape Turing machine,Theoretical Computer Science 85 (1991), 205–212.
A. R. Meyer and M. J. Fischer, Economy of description by automata, grammars, and formal systems,Proceedings of the 21st IEEE Symposium on Switching and Automata Theory, 1971, pp. 188–191.
D. E. Muller and F. P. Preparata, Bounds to complexities of networks for sorting and switching,Journal of the Association for Computing Machinery 22 (1975), 97–111.
W. L. Ruzzo, Tree-size bounded alternation,Journal of Computer and System Sciences 21 (1980), 218–235.
W. L. Ruzzo, On uniform circuit complexity,Journal of Computer and System Sciences 22 (1981), 365–383.
John E. Savage,The Complexity of Computing, Wiley, New York, 1976, reprint by Krieger, 1987.
J. C. Shepherdson, The reduction of two-way automata to one-way automata,IBM Journal of Research and Development (1959), 198–200; also in E. F. Moore (ed.),Sequential Machines: Selected Papers, Addison-Wesley, Reading, MA, 1964.
M. Sipser, Lower bounds on the size of sweeping machines,Proceedings of the 11thACM Symposium on Theory of Computing, 1979, pp. 360–364; expanded inJournal of Computer and System Sciences 21 (1980), 195–202.
M. Sipser, Halting space-bounded computations,Theoretical Computer Science 10 (1980), 335–338. (See alsoProc. IEEE FOCS, 1978.)
F. N. Springsteel, “On the pre-AFL of [logn] space, and related families of languages,Theoretical Computer Science 2 (1976), 295–304.
W. Sakoda and M. Sipser, Non-determinism and the size of two-way automata,Proceedings of the 10thACM Symposium on Theory of Computing, 1978, pp. 275–286.
J. van Leeuwen (ed.),Handbook of Theoretical Computer Science, Vol. A, MIT Press, Cambridge, MA, and Elsevier, Amsterdam, 1990.
I. Wegener,The Complexity of Boolean Functions, Wiley-Teubner Series in Computer Science, Wiley, New York, 1987.
Author information
Authors and Affiliations
Additional information
This research was supported in part by N.S.F. Grant DMS 8702019.
Rights and permissions
About this article
Cite this article
Birget, J.C. Two-way automata and length-preserving homomorphisms. Math. Systems Theory 29, 191–226 (1996). https://doi.org/10.1007/BF01201276
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01201276