Determination of finite automata accepting subregular languages

DOI10.1016/j.tcs.2009.05.019zbMath1173.68030OpenAlexW2010487137MaRDI QIDQ2271457

Martin Kutrib, Markus Holzer, Henning Bordihn

Publication date: 7 August 2009

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

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

zbMATH Keywords

finite automatastate complexitydeterminationsubregular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (25)

State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ Networks of evolutionary processors: the power of subregular filters ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES ⋮ Solutions to four open problems concerning controlled pure grammar systems ⋮ Aspects of Reversibility for Classical Automata ⋮ Nondeterministic operational complexity in subregular languages ⋮ Operational complexity in subregular classes ⋮ State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ State complexity of combined operations with two basic operations ⋮ Nondeterministic state complexity of star-free languages ⋮ On external contextual grammars with subregular selection languages ⋮ On a structural property in the state complexity of projected regular languages ⋮ Incomplete operational transition complexity of regular languages ⋮ Finite automata with undirected state graphs ⋮ Nondeterministic State Complexity of Star-Free Languages ⋮ Descriptional Complexity of Bounded Regular Languages ⋮ State Complexity of Prefix Distance of Subregular Languages ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Descriptional complexity of regular languages ⋮ Square on Ideal, Closed and Free Languages ⋮ On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata ⋮ Closure properties of subregular languages under operations ⋮ Operations on subregular languages and nondeterministic state complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On NFAs where all states are final, initial, or both
• Finite automata and unary languages
• Multiple-entry finite automata
• Locally testable languages
• Characterizations of locally testable events
• Power-separating regular languages
• Ultimate-Definite and Symmetric-Definite Events and Automata
• On finite monoids having only trivial subgroups
• Lower Bound of the Number of Threshold Functions
• The Theory of Definite Automata
• Roots of Star Events
• On Decompositions of Regular Events
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata

This page was built for publication: Determination of finite automata accepting subregular languages