\(L(A)=L(B)\)? decidability results from complete formal systems
From MaRDI portal
Publication:1589483
DOI10.1016/S0304-3975(00)00285-1zbMath0957.68051WikidataQ56386810 ScholiaQ56386810MaRDI QIDQ1589483
Publication date: 12 December 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
finite-dimensional vector spacesdeterministic pushdown automatarational seriescomplete formal systemsmatrix semi-groups
Related Items (35)
Some decision problems concerning semilinearity and commutation. ⋮ Word problems of groups: formal languages, characterizations and decidability ⋮ An approach to deciding the observational equivalence of Algol-like languages ⋮ Rational subsets of partially reversible monoids ⋮ Bisimulation equivalence and regularity for real-time one-counter automata ⋮ A note on controllability of deterministic context-free~systems ⋮ A generic framework for checking semantic equivalences between pushdown automata and finite-state automata ⋮ Decision problems for pushdown threads ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ The different shades of infinite session types ⋮ Queue Automata: Foundations and Developments ⋮ On the Density of Context-Free and Counter Languages ⋮ Equivalence of pushdown automata via first-order grammars ⋮ Selected Ideas Used for Decidability and Undecidability of Bisimilarity ⋮ Quasi-rocking real-time pushdown automata ⋮ Equivalence of deterministic pushdown automata revisited ⋮ Self-Verifying Pushdown and Queue Automata ⋮ Language equivalence of probabilistic pushdown automata ⋮ THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE ⋮ On the computational complexity of bisimulation, redux ⋮ Some properties of iterated languages ⋮ Decidability of DPDA equivalence ⋮ A general approach to comparing infinite-state systems with their finite-state specifications ⋮ Formal languages over GF(2) ⋮ Simplification Problems for Deterministic Pushdown Automata on Infinite Words ⋮ UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES ⋮ Highly Undecidable Problems For Infinite Computations ⋮ Set Automata ⋮ Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence ⋮ Optimally Resilient Strategies in Pushdown Safety Games ⋮ Universality Problem for Unambiguous VASS ⋮ A NOTE ON LIMITED PUSHDOWN ALPHABETS IN STATELESS DETERMINISTIC PUSHDOWN AUTOMATA ⋮ Model-Checking Games for Typed λ-Calculi ⋮ \(L(A)=L(B)\)? A simplified decidability proof.
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
- Unnamed Item
- The equivalence problem of multitape finite automata
- The monadic second-order logic of graphs. IV: Definability properties of equational graphs
- Some decision problems about controlled rewriting systems
- Fundamental properties of infinite trees
- Pushdown machines for the macro tree transducer
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
- A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- A representation of trees by languages. II
- On the decidability of equivalence for deterministic pushdown transducers
- DPDA's in 'Atomic normal form' and applications to equivalence problems
- The IO- and OI-hierarchies
- The equivalence problem for LL- and LR-regular grammars
- Deterministic one-counter automata
- Program equivalence and context-free grammars
- Equivalence problems for deterministic context-free languages and monadic recursion schemes
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- A representation of trees by languages. I
- On equivalence of grammars through transformation trees
- A polynomial algorithm for deciding bisimilarity of normed context-free processes
- Decidability of the equivalence problem for deterministic pushdown automata
- Synchronizable deterministic pushdown automata and the decidability of their equivalence
- Regular expressions and the equivalence of programs
- On formalised computer programs
- Equivalences on program schemes
- The equivalence problem for real-time deterministic pushdown automata
- Decidability of bisimulation equivalence for process generating context-free languages
- n-Rational Algebras I. Basic Properties and Free Algebras
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width
- An axiomatic approach to the Korenjak-Hopcroft algorithms
- Iterated linear control and iterated one-turn pushdowns
- The equivalence problem for real-time DPDAs
- Graph expressions and graph rewritings
- The equivalence problem for real-time strict deterministic languages
- A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
- The equivalence problem for real-time strict deterministic pushdown automata
- Bisimulation equivalence is decidable for one-counter processes
- The equivalence problem for deterministic pushdown automata is decidable
- The equivalence problem for deterministic finite-turn pushdown automata
- Deterministic context free languages
- Two Families of Languages Related to ALGOL
- Properties of deterministic top-down grammars
- On the translation of languages from left to right
- On Ianov's Program Schemata
- On context-free languages and push-down automata
- Decidability of bisimulation equivalence for normed pushdown processes
This page was built for publication: \(L(A)=L(B)\)? decidability results from complete formal systems
