Descriptional complexity of regular languages

DOI10.4171/Automata-1/12MaRDI QIDQ2074214

Hermann Gruber, Markus Holzer, Martin Kutrib

Publication date: 4 February 2022

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Head and state hierarchies for unary multi-head finite automata
• From regular expressions to deterministic automata
• On the state complexity of reversals of regular languages
• On equations for regular languages, finite automata, and sequential networks
• On the size of inverse semigroups given by generators
• A lower bound technique for the size of nondeterministic finite automata
• Partial derivatives of regular expressions and finite automaton constructions
• Partial orders on words, minimal elements of regular languages, and state complexity
• On deterministic finite automata and syntactic monoid size
• The state complexity of \(L^{2}\) and \(L^k\)
• Succinct description of regular languages by weak restarting automata
• Lower bounds for the transition complexity of NFAs
• On the efficient construction of quasi-reversible automata for reversible languages
• Succinctness of regular expressions with interleaving, intersection and counting
• Unary finite automata vs. arithmetic progressions
• State complexity of power
• State complexity of basic operations on suffix-free regular languages
• On NFAs where all states are final, initial, or both
• The complexity of restricted regular expressions and the synthesis problem for finite automata
• Finite automata and unary languages
• Algorithms for determining relative star height and star height
• Amounts of nondeterminism in finite automata
• Lower bounds on the size of sweeping automata
• Succinct representation of regular languages by Boolean automata
• Intersection and union of regular languages and state complexity
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Complexity measures for regular expressions
• Some remarks on multiple-entry finite automata
• Learning approximately regular languages with reversible languages
• Regular expressions into finite automata
• The state complexities of some basic operations on regular languages
• A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
• Follow automata.
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• Operations on Boolean and alternating finite automata
• Quotient complexity of closed languages
• Reversible nondeterministic finite automata
• State complexity of some operations on binary regular languages
• Complementing unary nondeterministic automata
• Multiple-entry finite automata
• Quotient complexity of ideal languages
• On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
• Determination of finite automata accepting subregular languages
• Language operations with regular expressions of polynomial size
• Comparing the size of NFAs with and without \(\epsilon\)-transitions
• Square on deterministic, alternating, and Boolean finite automata
• Concise representations of reversible automata
• Theory of átomata
• Magic numbers in the state hierarchy of finite automata
• On the average state and transition complexity of finite languages
• The size of Higman-Haines sets
• Transition graphs and the star-height of regular events
• Minimizing nfa's and regular expressions
• Optimal Simulations between Unary Automata
• A Lower Bound For Reversible Automata
• Limited Automata and Context-Free Languages
• Universal Witnesses for State Complexity of Boolean Operations and Concatenation Combined with Star
• Descriptional Complexity of Operations on Alternating and Boolean Automata
• Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
• Succinctness of the Complement and Intersection of Regular Expressions
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• MAGIC NUMBERS AND TERNARY ALPHABET
• An Optimal Construction of Finite Automata from Regular Expressions
• Large Aperiodic Semigroups
• A geometrical view of the determinization and minimization of finite-state automata
• Automata Studies. (AM-34)
• THE ABSTRACT THEORY OF AUTOMATA
• Minimal Reversible Deterministic Finite Automata
• Constructions for alternating finite automata^∗
• State complexity of cyclic shift
• OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA
• On the State Complexity of Operations on Two-Way Finite Automata
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
• Simplifying Regular Expressions
• Some Minimality Results on Biresidual and Biseparable Automata
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• Minimal NFA and biRFSA Languages
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• Implementation of State Elimination Using Heuristics
• Short Regular Expressions from Finite Automata: Empirical Results
• Alternation
• Inference of Reversible Languages
• Homomorphisms that preserve star height
• Rankings of Graphs
• The Degree of Irreversibility in Deterministic Finite Automata
• Bounded-reversal multihead finite automata languages
• QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
• On the State Complexity of Scattered Substrings and Superstrings
• Restarting automata
• PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA
• SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES
• SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA
• LIMITED AUTOMATA AND REGULAR LANGUAGES
• State-complexity of finite-state devices, state compressibility and incompressibility
• NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
• Universal Witnesses for State Complexity of Basic Operations Combined with Reversal
• IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Regular Expressions and NFAs Without ε-Transitions
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• Implementation and Application of Automata
• Mathematical Foundations of Computer Science 2005
• COMPLEXITY OF ATOMS OF REGULAR LANGUAGES
• Upper Bound on Syntactic Complexity of Suffix-Free Languages
• On Simulation Cost of Unary Limited Automata
• Programming Techniques: Regular expression search algorithm
• The loop complexity of pure-group events
• A generalization of context-free determinism
• On the State Minimization of Nondeterministic Finite Automata
• On free monoids partially ordered by embedding
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Logic for Programming, Artificial Intelligence, and Reasoning
• A Unified Construction of the Glushkov, Follow, and Antimirov Automata
• Ordering by Divisibility in Abstract Algebras
• More on the Size of Higman-Haines Sets: Effective Constructions
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
• Complexity of atoms, combinatorially
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item