Descriptional complexity of regular languages
type: Item
instance of: scholarly article
title: Descriptional complexity of regular languages
author: Hermann Gruber
author: Markus Holzer
author: Martin Kutrib
publication date: 2022-02-04T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7469510
MaRDI profile type: Publication
cites work: Implementation of State Elimination Using Heuristics
cites work: Q4091421
cites work: A Unified Construction of the Glushkov, Follow, and Antimirov Automata
cites work: Q5306170
cites work: Inference of Reversible Languages
cites work: Partial derivatives of regular expressions and finite automaton constructions
cites work: Q4005202
cites work: The Degree of Irreversibility in Deterministic Finite Automata
cites work: On the size of inverse semigroups given by generators
cites work: From regular expressions to deterministic automata
cites work: Logic for Programming, Artificial Intelligence, and Reasoning
cites work: Q5417708
cites work: Intersection and union of regular languages and state complexity
cites work: Partial orders on words, minimal elements of regular languages, and state complexity
cites work: State-complexity of finite-state devices, state compressibility and incompressibility
cites work: Rankings of Graphs
cites work: Determination of finite automata accepting subregular languages
cites work: Regular expressions into finite automata
cites work: Quotient complexity of ideal languages
cites work: Quotient complexity of closed languages
cites work: Quotient complexity of regular languages
cites work: IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
cites work: Q4994941
cites work: On equations for regular languages, finite automata, and sequential networks
cites work: SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES
cites work: Q5178449
cites work: Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
cites work: QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
cites work: Universal Witnesses for State Complexity of Basic Operations Combined with Reversal
cites work: Universal Witnesses for State Complexity of Boolean Operations and Concatenation Combined with Star
cites work: Upper Bound on Syntactic Complexity of Suffix-Free Languages
cites work: Large Aperiodic Semigroups
cites work: Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
cites work: COMPLEXITY OF ATOMS OF REGULAR LANGUAGES
cites work: Theory of átomata
cites work: Q4474150
cites work: Q4807824
cites work: NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
cites work: Alternation
cites work: Finite automata and unary languages
cites work: A geometrical view of the determinization and minimization of finite-state automata
cites work: Implementation and Application of Automata
cites work: State complexity of power
cites work: Lower bounds for the transition complexity of NFAs
cites work: Transition graphs and the star-height of regular events
cites work: Complexity measures for regular expressions
cites work: Q5437181
cites work: Constructions for alternating finite automata∗
cites work: Q4590910
cites work: On the efficient construction of quasi-reversible automata for reversible languages
cites work: Magic numbers in the state hierarchy of finite automata
cites work: Succinctness of regular expressions with interleaving, intersection and counting
cites work: Succinctness of the Complement and Intersection of Regular Expressions
cites work: Multiple-entry finite automata
cites work: A lower bound technique for the size of nondeterministic finite automata
cites work: THE ABSTRACT THEORY OF AUTOMATA
cites work: Minimizing nfa's and regular expressions
cites work: Simplifying Regular Expressions
cites work: Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
cites work: On the average state and transition complexity of finite languages
cites work: Finding Lower Bounds for Nondeterministic State Complexity Is Hard
cites work: Language operations with regular expressions of polynomial size
cites work: Tight Bounds on the Descriptional Complexity of Regular Expressions
cites work: PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA
cites work: The size of Higman-Haines sets
cites work: More on the Size of Higman-Haines Sets: Effective Constructions
cites work: Short Regular Expressions from Finite Automata: Empirical Results
cites work: Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
cites work: An Optimal Construction of Finite Automata from Regular Expressions
cites work: On free monoids partially ordered by embedding

Descriptional complexity of regular languages (cites work)
cites work: STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES

Descriptional complexity of regular languages (cites work)
cites work: State complexity of basic operations on suffix-free regular languages

Descriptional complexity of regular languages (cites work)
cites work: Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages

Descriptional complexity of regular languages (cites work)
cites work: Algorithms for determining relative star height and star height

Descriptional complexity of regular languages (cites work)
cites work: Homomorphisms that preserve star height

Descriptional complexity of regular languages (cites work)
cites work: A lower bound for reversible automata

Descriptional complexity of regular languages (cites work)
cites work: A generalization of context-free determinism

Descriptional complexity of regular languages (cites work)
cites work: Ordering by Divisibility in Abstract Algebras

Descriptional complexity of regular languages (cites work)
cites work: Minimal Reversible Deterministic Finite Automata

Descriptional complexity of regular languages (cites work)
cites work: On deterministic finite automata and syntactic monoid size

Descriptional complexity of regular languages (cites work)
cites work: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES

Descriptional complexity of regular languages (cites work)
cites work: Reversible nondeterministic finite automata

Descriptional complexity of regular languages (cites work)
cites work: Q4531373

Descriptional complexity of regular languages (cites work)
cites work: Q3862379

Descriptional complexity of regular languages (cites work)
cites work: Operations on Boolean and alternating finite automata

Descriptional complexity of regular languages (cites work)
cites work: Q4337605

Descriptional complexity of regular languages (cites work)
cites work: Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata

Descriptional complexity of regular languages (cites work)
cites work: On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's

Descriptional complexity of regular languages (cites work)
cites work: Comparing the size of NFAs with and without \(\epsilon\)-transitions

Descriptional complexity of regular languages (cites work)
cites work: A note on semilinear sets and bounded-reversal multihead pushdown automata

Descriptional complexity of regular languages (cites work)
cites work: Follow automata.

Descriptional complexity of regular languages (cites work)
cites work: Complexity of atoms, combinatorially

Descriptional complexity of regular languages (cites work)
cites work: Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs

Descriptional complexity of regular languages (cites work)
cites work: A family of NFAs which need 2\(^{n}-\alpha\) deterministic states

Descriptional complexity of regular languages (cites work)
cites work: Restarting automata

Descriptional complexity of regular languages (cites work)
cites work: STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION

Descriptional complexity of regular languages (cites work)
cites work: DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET

Descriptional complexity of regular languages (cites work)
cites work: Q4779161

Descriptional complexity of regular languages (cites work)
cites work: State complexity of some operations on binary regular languages

Descriptional complexity of regular languages (cites work)
cites work: MAGIC NUMBERS AND TERNARY ALPHABET

Descriptional complexity of regular languages (cites work)
cites work: Descriptional Complexity of Operations on Alternating and Boolean Automata

Descriptional complexity of regular languages (cites work)
cites work: On the State Complexity of Operations on Two-Way Finite Automata

Descriptional complexity of regular languages (cites work)
cites work: State complexity of cyclic shift

Descriptional complexity of regular languages (cites work)
cites work: On the State Minimization of Nondeterministic Finite Automata

Descriptional complexity of regular languages (cites work)
cites work: On NFAs where all states are final, initial, or both

Descriptional complexity of regular languages (cites work)
cites work: Mathematical Foundations of Computer Science 2005

Descriptional complexity of regular languages (cites work)
cites work: Q4503150

Descriptional complexity of regular languages (cites work)
cites work: Amounts of nondeterminism in finite automata

Descriptional complexity of regular languages (cites work)
cites work: Automata Studies. (AM-34)

Descriptional complexity of regular languages (cites work)
cites work: Learning approximately regular languages with reversible languages

Descriptional complexity of regular languages (cites work)
cites work: Square on deterministic, alternating, and Boolean finite automata

Descriptional complexity of regular languages (cites work)
cites work: STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET

Descriptional complexity of regular languages (cites work)
cites work: Head and state hierarchies for unary multi-head finite automata

Descriptional complexity of regular languages (cites work)
cites work: SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA

Descriptional complexity of regular languages (cites work)
cites work: OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA

Descriptional complexity of regular languages (cites work)
cites work: Succinct description of regular languages by weak restarting automata

Descriptional complexity of regular languages (cites work)
cites work: On Simulation Cost of Unary Limited Automata

Descriptional complexity of regular languages (cites work)
cites work: Minimal NFA and biRFSA Languages

Descriptional complexity of regular languages (cites work)
cites work: Q4609331

Descriptional complexity of regular languages (cites work)
cites work: Q5016365

Descriptional complexity of regular languages (cites work)
cites work: Concise representations of reversible automata

Descriptional complexity of regular languages (cites work)
cites work: The complexity of restricted regular expressions and the synthesis problem for finite automata

Descriptional complexity of regular languages (cites work)
cites work: Succinct representation of regular languages by Boolean automata

Descriptional complexity of regular languages (cites work)
cites work: Q4737155

Descriptional complexity of regular languages (cites work)
cites work: Q5554980

Descriptional complexity of regular languages (cites work)
cites work: Q5628039

Descriptional complexity of regular languages (cites work)
cites work: The loop complexity of pure-group events

Descriptional complexity of regular languages (cites work)
cites work: Q5536277

Descriptional complexity of regular languages (cites work)
cites work: Complementing unary nondeterministic automata

Descriptional complexity of regular languages (cites work)
cites work: Optimal simulations between unary automata

Descriptional complexity of regular languages (cites work)
cites work: On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata

Descriptional complexity of regular languages (cites work)
cites work: Q4941905

Descriptional complexity of regular languages (cites work)
cites work: On the State Complexity of Scattered Substrings and Superstrings

Descriptional complexity of regular languages (cites work)
cites work: LIMITED AUTOMATA AND REGULAR LANGUAGES

Descriptional complexity of regular languages (cites work)
cites work: Limited automata and context-free languages

Descriptional complexity of regular languages (cites work)
cites work: UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION

Descriptional complexity of regular languages (cites work)
cites work: Q5541339

Descriptional complexity of regular languages (cites work)
cites work: The state complexity of \(L^{2}\) and \(L^k\)

Descriptional complexity of regular languages (cites work)
cites work: Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation

Descriptional complexity of regular languages (cites work)
cites work: On the state complexity of reversals of regular languages

Descriptional complexity of regular languages (cites work)
cites work: Q4390537

Descriptional complexity of regular languages (cites work)
cites work: Regular Expressions and NFAs Without ε-Transitions

Descriptional complexity of regular languages (cites work)
cites work: Q5541340

Descriptional complexity of regular languages (cites work)
cites work: Q4040284

Descriptional complexity of regular languages (cites work)
cites work: Lower bounds on the size of sweeping automata

Descriptional complexity of regular languages (cites work)
cites work: Q4131648

Descriptional complexity of regular languages (cites work)
cites work: Bounded-reversal multihead finite automata languages

Descriptional complexity of regular languages (cites work)
cites work: Some Minimality Results on Biresidual and Biseparable Automata

Descriptional complexity of regular languages (cites work)
cites work: Programming Techniques: Regular expression search algorithm

Descriptional complexity of regular languages (cites work)
cites work: Unary finite automata vs. arithmetic progressions

Descriptional complexity of regular languages (cites work)
cites work: Some remarks on multiple-entry finite automata

Descriptional complexity of regular languages (cites work)
cites work: Q4848749

Descriptional complexity of regular languages (cites work)
cites work: State complexity of regular languages

Descriptional complexity of regular languages (cites work)
cites work: Q3152811

Descriptional complexity of regular languages (cites work)
cites work: The state complexities of some basic operations on regular languages

Descriptional complexity of regular languages (DOI)
DOI: 10.4171/AUTOMATA-1/12