On the descriptional complexity of finite automata with modified acceptance conditions

DOI10.1016/J.TCS.2004.06.030zbMath1078.68085OpenAlexW2050769871MaRDI QIDQ1763715

Markus Holzer, Martin Kutrib

Publication date: 22 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.06.030

zbMATH Keywords

Finite automataDescriptional complexityAcceptance conditionsComputational power

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• A lower bound technique for the size of nondeterministic finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Degree-languages: A new concept of acceptance
• The state complexities of some basic operations on regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Concise representations of regular languages by degree and probabilistic finite automata
• Propositional dynamic logic of looping and converse is elementarily decidable
• Decision problems forω-automata
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the descriptional complexity of finite automata with modified acceptance conditions