Lower bound technique for length-reducing automata

DOI10.1016/j.ic.2007.02.003zbMath1127.68051MaRDI QIDQ2381504

Tomasz Jurdziński, Krzysztof Loryś

Publication date: 18 September 2007

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2007.02.003

zbMATH Keywords

Kolmogorov complexity; string rewriting; Automata and formal languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

68Q42: Grammars and rewriting systems

Related Items

Probabilistic length-reducing two-pushdown automata, A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems, ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA

Uses Software

• UCFL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Membership for growing context-sensitive grammars is polynomial
• Growing context-sensitive languages and Church-Rosser languages
• McNaughton families of languages.
• The context-splittable normal form for Church-Rosser language systems.
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Boolean grammars
• On certain formal properties of grammars
• The Boolean Closure of Growing Context-Sensitive Languages
• Church-Rosser Thue systems and formal languages
• On growing context-sensitive languages
• Fundamentals of Computation Theory
• The parsing for general phrase-structure grammars
• Probabilistic Length-Reducing Automata