Language equations
From MaRDI portal
Publication:2074222
DOI10.4171/Automata-1/21MaRDI QIDQ2074222
Alexander Okhotin, Michal Kunc
Publication date: 4 February 2022
Related Items
Uses Software
Cites Work
- 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
- Equations over sets of integers with addition only
- Parsing by matrix multiplication generalized to Boolean grammars
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- On the expressive power of univariate equations over sets of natural numbers
- On the number of nonterminals in linear conjunctive grammars
- On equations for regular languages, finite automata, and sequential networks
- Complexity of equations over sets of natural numbers
- One-nonterminal conjunctive grammars over a unary alphabet
- On real time one-way cellular array
- Representing hyper-arithmetical sets by equations over sets of integers
- On regularity of context-free languages
- Language equations with complementation: expressive power
- Characterizations and computational complexity of systolic trellis automata
- Unresolved systems of language equations: expressive power and decision problems
- On the uniqueness of shuffle on words and finite languages
- Well-founded semantics for Boolean grammars
- Language equations with complementation: decision problems
- Decision problems for language equations
- Conjunctive grammars with restricted disjunction
- Conjugacy of finite biprefix codes
- Variations of the firing squad problem and applications
- Shuffle on trajectories: Syntactic constraints
- A note on language equations involving morphisms
- Unrestricted complementation in language equations over a one-letter alphabet
- On language equations with invertible operations
- Polynomial closure of group languages and open sets of the Hall topology
- Conjunctive grammars and systems of language equations
- The equivalence problem for finite substitutions in a regular language
- Boolean grammars
- Computational completeness of equations over sets of natural numbers
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- Simple equations on binary factorial languages
- Playing with Conway's problem
- A Burnside approach to the finite substitution problem
- Complexity of regular language matching and other decidable cases of the satisfiability problem for constraints between regular open terms
- On effective construction of the greatest solution of language inequality \(XA\subseteq BX\)
- Commutation with codes
- Decidability of trajectory-based equations
- Regular solutions of language inequalities and well quasi-orders
- The power of commuting with finite sets of words
- Solving Language Equations and Disequations with Applications to Disunification in Description Logics and Monadic Set Constraints
- Equations X + A = B and (X + X) + C = (X − X) + D over Sets of Natural Numbers
- Unification in a Description Logic with Transitive Closure of Roles
- SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES
- ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS
- On the unique satisfiability problem
- BOOLEAN FUZZY SETS
- On the simplest centralizer of a language
- On language equations with concatenation and various sets of Boolean operations
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- On Language Equations XXK = XXL and XM = N over a Unary Alphabet
- Systolic trellis automatat†
- Equations between Regular Terms and an Application to Process Logic
- One-way bounded cellular automata
- Finite loops recognize exactly the regular open languages
- On the equivalence of linear conjunctive grammars and trellis automata
- Algebraic Systems and Pushdown Automata
- The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable
- Developments in Language Theory
- Mathematical Foundations of Computer Science 2005
- Systems of equations in the algebra of events
- Three models for the description of language
- Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
- Two Families of Languages Related to ALGOL
- The Equivalence Problem of Finite Substitutions on ab*c, with Applications
- Unification of concept terms in description logics