Chrobak Normal Form Revisited, with Applications

DOI10.1007/978-3-642-22256-6_14zbMath1297.68130OpenAlexW126002049WikidataQ63071609 ScholiaQ63071609MaRDI QIDQ5200060

Paweł Gawrychowski

Publication date: 29 July 2011

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22256-6_14

zbMATH Keywords

descriptional complexityunary automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

String theories involving regular membership predicates: from practice to theory and back, Approximate membership for regular languages modulo the edit distance, Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata, Towards more efficient methods for solving regular-expression heavy string constraints, Operational state complexity of unary NFAs with finite nondeterminism, Binary coded unary regular languages, Nondeterministic syntactic complexity, Enhancing unsatisfiable cores for LTL with information on temporal relevance, Automata for unordered trees, Investigations on Automata and Languages Over a Unary Alphabet, Optimal state reductions of automata with partially specified behaviors

Cites Work

• Unnamed Item
• Unary finite automata vs. arithmetic progressions
• Finite automata and unary languages
• Simulating finite automata with context-free grammars.
• Magic numbers in the state hierarchy of finite automata
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA
• On Context-Free Languages
• On a linear diophantine problem of Frobenius