Descriptional complexity of regular languages
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1820028 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 58314 (Why is no real title available?)
- scientific article; zbMATH DE number 193480 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 1011685 (Why is no real title available?)
- scientific article; zbMATH DE number 1156489 (Why is no real title available?)
- scientific article; zbMATH DE number 2081044 (Why is no real title available?)
- scientific article; zbMATH DE number 1502109 (Why is no real title available?)
- scientific article; zbMATH DE number 1747444 (Why is no real title available?)
- scientific article; zbMATH DE number 2086620 (Why is no real title available?)
- scientific article; zbMATH DE number 1834665 (Why is no real title available?)
- scientific article; zbMATH DE number 1916664 (Why is no real title available?)
- scientific article; zbMATH DE number 798342 (Why is no real title available?)
- scientific article; zbMATH DE number 1418342 (Why is no real title available?)
- scientific article; zbMATH DE number 7444007 (Why is no real title available?)
- scientific article; zbMATH DE number 3251424 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3254906 (Why is no real title available?)
- scientific article; zbMATH DE number 3269886 (Why is no real title available?)
- scientific article; zbMATH DE number 3353192 (Why is no real title available?)
- A Unified Construction of the Glushkov, Follow, and Antimirov Automata
- A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
- A generalization of context-free determinism
- A geometrical view of the determinization and minimization of finite-state automata
- A lower bound for reversible automata
- A lower bound technique for the size of nondeterministic finite automata
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- A survey on operational state complexity
- Algorithms for determining relative star height and star height
- Alternation
- Amounts of nondeterminism in finite automata
- An optimal construction of finite automata from regular expressions
- Automata Studies. (AM-34)
- Bounded-reversal multihead finite automata languages
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- Complementing unary nondeterministic automata
- Complexity measures for regular expressions
- Complexity of atoms of regular languages
- Complexity of atoms, combinatorially
- Concise representations of reversible automata
- Constructions for alternating finite automata∗
- DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
- Descriptional Complexity of Operations on Alternating and Boolean Automata
- Determination of finite automata accepting subregular languages
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Finite automata and unary languages
- Follow automata.
- From regular expressions to deterministic automata
- Head and state hierarchies for unary multi-head finite automata
- Homomorphisms that preserve star height
- Implementation and Application of Automata
- Implementation of State Elimination Using Heuristics
- In search of most complex regular languages
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Inference of Reversible Languages
- Intersection and union of regular languages and state complexity
- Language operations with regular expressions of polynomial size
- Languages convex with respect to binary relations, and their closure properties
- Large Aperiodic Semigroups
- Learning approximately regular languages with reversible languages
- Limited automata and context-free languages
- Limited automata and regular languages
- Logic for Programming, Artificial Intelligence, and Reasoning
- Lower bounds for the transition complexity of NFAs
- Lower bounds on the size of sweeping automata
- Magic numbers and ternary alphabet
- Magic numbers in the state hierarchy of finite automata
- Mathematical Foundations of Computer Science 2005
- Maximally atomic languages
- Minimal NFA and biRFSA Languages
- Minimal and reduced reversible automata
- Minimal reversible deterministic finite automata
- Minimizing nfa's and regular expressions
- More on the Size of Higman-Haines Sets: Effective Constructions
- Multiple-entry finite automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
- Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
- OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA
- On NFAs where all states are final, initial, or both
- On deterministic finite automata and syntactic monoid size
- On equations for regular languages, finite automata, and sequential networks
- On free monoids partially ordered by embedding
- On simulation cost of unary limited automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- On the State Complexity of Operations on Two-Way Finite Automata
- On the State Minimization of Nondeterministic Finite Automata
- On the average state and transition complexity of finite languages
- On the efficient construction of quasi-reversible automata for reversible languages
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- On the size of inverse semigroups given by generators
- On the state complexity of reversals of regular languages
- On the state complexity of scattered substrings and superstrings
- Operations on Boolean and alternating finite automata
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Optimal simulations between unary automata
- Ordering by Divisibility in Abstract Algebras
- Partial derivatives of regular expressions and finite automaton constructions
- Partial orders on words, minimal elements of regular languages, and state complexity
- Programming Techniques: Regular expression search algorithm
- Provably shorter regular expressions from finite automata
- QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
- Quotient complexity of ideal languages
- Quotient complexity of regular languages
- Rankings of Graphs
- Regular Expressions and NFAs Without ε-Transitions
- Regular expression matching with multi-strings and intervals
- Regular expressions into finite automata
- Regular expressions: new results and open problems
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Restarting automata
- Reversible nondeterministic finite automata
- STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
- Short Regular Expressions from Finite Automata: Empirical Results
- Simplifying regular expressions. A quantitative perspective
- Simulations of unary one-way multi-head finite automata
- Some Minimality Results on Biresidual and Biseparable Automata
- Some remarks on multiple-entry finite automata
- Square on deterministic, alternating, and Boolean finite automata
- State complexity of basic operations on suffix-free regular languages
- State complexity of cyclic shift
- State complexity of power
- State complexity of regular languages
- State complexity of some operations on binary regular languages
- State-complexity of finite-state devices, state compressibility and incompressibility
- Succinct description of regular languages by weak restarting automata
- Succinct representation of regular languages by Boolean automata
- Succinctness of regular expressions with interleaving, intersection and counting
- Succinctness of the Complement and Intersection of Regular Expressions
- Syntactic complexities of six classes of star-free languages
- Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular languages
- Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
- THE ABSTRACT THEORY OF AUTOMATA
- The complexity of restricted regular expressions and the synthesis problem for finite automata
- The degree of irreversibility in deterministic finite automata
- The loop complexity of pure-group events
- The size of Higman-Haines sets
- The state complexities of some basic operations on regular languages
- The state complexity of \(L^{2}\) and \(L^k\)
- Theory of átomata
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
- Transition graphs and the star-height of regular events
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- Unary finite automata vs. arithmetic progressions
- Universal witnesses for state complexity of Boolean operations and concatenation combined with star
- Universal witnesses for state complexity of basic operations combined with reversal
- Upper bound on syntactic complexity of suffix-free languages
- Upper bounds on syntactic complexity of left and two-sided ideals
Cited in
(27)- Implementation and Application of Automata
- Closure properties and descriptional complexity of deterministic regular expressions
- Descriptional complexity -- an introductory survey
- In Search of Most Complex Regular Languages
- Regular languages: to finite automata and beyond (invited talk)
- Descriptional complexity of bounded regular languages
- Simple regular expressions and languages
- A Logical Descriptor for Regular Languages via Stone Duality
- Regularity and size of set automata
- Descriptional complexity of deterministic regular expressions
- More Concise Representation of Regular Languages by Automata and Regular Expressions
- The complexity of regular(-like) expressions
- scientific article; zbMATH DE number 1773094 (Why is no real title available?)
- Descriptional complexity of bounded regular languages
- More concise representation of regular languages by automata and regular expressions
- Descriptional complexity of finite automata -- selected highlights
- scientific article; zbMATH DE number 4049104 (Why is no real title available?)
- Concatenation of Regular Languages and Descriptional Complexity
- scientific article; zbMATH DE number 7699973 (Why is no real title available?)
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- scientific article; zbMATH DE number 6136496 (Why is no real title available?)
- Determination of finite automata accepting subregular languages
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Recent trends in descriptional complexity of formal languages
- scientific article; zbMATH DE number 1860666 (Why is no real title available?)
- scientific article; zbMATH DE number 2201365 (Why is no real title available?)
This page was built for publication: Descriptional complexity of regular languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2074214)
