article

Limited Automata and Context-Free Languages

Authors:

Giovanni Pighizzini,

Andrea PisoniAuthors Info & Claims

Fundamenta Informaticae, Volume 136, Issue 1-2

Pages 157 - 176

Published: 01 January 2015 Publication History

Abstract

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages.

References

[1]

Blum, N., Koch, R.: Greibach Normal Form Transformation Revisited, Information and Computation, 150(1), 1999, 112-118, ISSN 0890-5401.

Digital Library

Google Scholar

[2]

Chomsky, N., Schützenberger, M.: The Algebraic Theory of Context-Free Languages, in: Computer Programming and Formal Systems (P. Braffort, D. Hirschberg, Eds.), vol. 35 of Studies in Logic and the Foundations of Mathematics, Elsevier, 1963, 118-161.

Google Scholar

[3]

Goldstine, J., Kappes, M., Kintala, C. M. R., Leung, H., Malcher, A., Wotschke, D.: Descriptional Complexity of Machines with Limited Resources, J. UCS, 8(2), 2002, 193-234.

Google Scholar

[4]

Harrison, M. A.: Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1978, ISBN 0201029553.

Google Scholar

[5]

Hibbard, T. N.: A Generalization of Context-Free Determinism, Information and Control, 11(1/2), 1967, 196-238.

Crossref

Google Scholar

[6]

Holzer, M., Kutrib, M.: Descriptional Complexity -- An Introductory Survey, in: Scientific Applications of Language Methods, chapter 1, Imperial College Press, 2010, 1-58.

Google Scholar

[7]

Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.

Digital Library

Google Scholar

[8]

Pighizzini, G., Pisoni, A.: Limited Automata and Regular Languages, in: Descriptional Complexity of Formal Systems (H. Jürgensen, R. Reis, Eds.), vol. 8031 of Lecture Notes in Computer Science, Springer, 2013, 253-264, An extended version will appear on the International Journal of Foundations of Computer Science.

Google Scholar

[9]

Pighizzini, G., Shallit, J., Wang, M.: Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds, J. Computer and System Sciences, 65(2), 2002, 393-414.

Crossref

Google Scholar

[10]

Shallit, J. O.: A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2008.

Digital Library

Google Scholar

[11]

Wagner, K.W., Wechsung, G.: Computational Complexity, D. Reidel Publishing Company, Dordrecht, 1986.

Google Scholar

Cited By

View all

Pighizzini GPrigioniero LSádovský Š(2024)Performing Regular Operations with 1-Limited AutomataTheory of Computing Systems10.1007/s00224-024-10163-168:3(465-486)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00224-024-10163-1
Pighizzini GPrigioniero LSádovský Š(2022)Performing Regular Operations with 1-Limited AutomataDevelopments in Language Theory10.1007/978-3-031-05578-2_19(239-250)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-05578-2_19
Yamakami T(2021)Between SC and LOGDCFL: Families of Languages Accepted by Polynomial-Time Logarithmic-Space Deterministic Auxiliary Depth-k Storage AutomataComputing and Combinatorics10.1007/978-3-030-89543-3_14(164-175)Online publication date: 24-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89543-3_14
Show More Cited By

Index Terms

Limited Automata and Context-Free Languages
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
2. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages
  2. Models of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Descriptional complexity of limited automata

A k-limited automaton is a linear bounded automaton that may rewrite each tape cell only in the first k visits, where k0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate the descriptional complexity ...
Complementing two-way finite automata

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, ...
Simulating finite automata with context-free grammars

We consider simulating finite automata (both deterministic and nondeterministic) with context-free grammars in Chomsky normal form (CNF). We show that any unary DFA with n states can be simulated by a CNF grammar with O(n^1/3) variables, and this bound ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Fundamenta Informaticae Volume 136, Issue 1-2

Non-Classical Models of Automata and Applications V

January 2015

196 pages

ISSN:0169-2968

Issue’s Table of Contents

Publisher

IOS Press

Netherlands

Publication History

Published: 01 January 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pighizzini GPrigioniero LSádovský Š(2024)Performing Regular Operations with 1-Limited AutomataTheory of Computing Systems10.1007/s00224-024-10163-168:3(465-486)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00224-024-10163-1
Pighizzini GPrigioniero LSádovský Š(2022)Performing Regular Operations with 1-Limited AutomataDevelopments in Language Theory10.1007/978-3-031-05578-2_19(239-250)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-05578-2_19
Yamakami T(2021)Between SC and LOGDCFL: Families of Languages Accepted by Polynomial-Time Logarithmic-Space Deterministic Auxiliary Depth-k Storage AutomataComputing and Combinatorics10.1007/978-3-030-89543-3_14(164-175)Online publication date: 24-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89543-3_14
Rubtsov A(2021)A Linear-Time Simulation of Deterministic d-Limited AutomataDevelopments in Language Theory10.1007/978-3-030-81508-0_28(342-354)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-81508-0_28
Yue JYan YChen Z(2020)Language acceptability of finite automata based on theory of semi‐tensor product of matricesAsian Journal of Control10.1002/asjc.219021:6(2634-2643)Online publication date: 23-Jan-2020
https://dl.acm.org/doi/10.1002/asjc.2190
Yamakami T(2019)Behavioral Strengths and Weaknesses of Various Models of Limited AutomataSOFSEM 2019: Theory and Practice of Computer Science10.1007/978-3-030-10801-4_40(519-530)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1007/978-3-030-10801-4_40
Kutrib MPighizzini GWendlandt M(2018)Descriptional complexity of limited automataInformation and Computation10.1016/j.ic.2017.09.005259:P2(259-276)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1016/j.ic.2017.09.005
Guillon BPrigioniero L(2018)Linear-Time Limited AutomataDescriptional Complexity of Formal Systems10.1007/978-3-319-94631-3_11(126-138)Online publication date: 25-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-94631-3_11
Yan YChen ZYue J(2017)Algebraic state space approach to model and control combined automataFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-5128-z11:5(874-886)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s11704-016-5128-z
Pighizzini G(2015)Guest ColumnACM SIGACT News10.1145/2818936.281894746:3(37-55)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1145/2818936.2818947

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Descriptional complexity of limited automata

Complementing two-way finite automata

Simulating finite automata with context-free grammars

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations