Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
From MaRDI portal
Publication:1853731
DOI10.1016/S0304-3975(01)00214-6zbMath1064.68050OpenAlexW2096207507WikidataQ56621425 ScholiaQ56621425MaRDI QIDQ1853731
Olivier Carton, Christophe Prieur, Marie-Pierre Béal, Jacques Sakarovitch
Publication date: 22 January 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00214-6
Related Items (34)
Crisp-determinization of weighted tree automata over strong bimonoids ⋮ Multi-sequential Word Relations ⋮ FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Visibly pushdown transducers ⋮ On the decidability of the valuedness problem for two-way finite transducers ⋮ Equivalence Checking Problem for Finite State Transducers over Semigroups ⋮ Two Effective Properties of ω-Rational Functions ⋮ On the continuity set of an Omega rational function ⋮ Unnamed Item ⋮ Efficient algorithms for computing the inner edit distance of a regular language via transducers ⋮ Lexicographic decomposition of \(k\)-valued transducers ⋮ On the Decidability of the Equivalence for k-Valued Transducers ⋮ FINITELY SUBSEQUENTIAL TRANSDUCERS ⋮ Multi-Sequential Word Relations ⋮ Over Which Monoids is the Transducer Determinization Procedure Applicable? ⋮ An optimal pre-determinization algorithm for weighted transducers ⋮ Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton ⋮ Sequential? ⋮ Space-efficient bimachine construction based on the equalizer accumulation principle ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Decidable weighted expressions with Presburger combinators ⋮ Unnamed Item ⋮ Finite sequentiality of unambiguous max-plus tree automata ⋮ Transducing reversibly with finite state machines ⋮ Unnamed Item ⋮ On the Decidability of the Equivalence for a Certain Class of Transducers ⋮ On Synthesis of Resynchronizers for Transducers ⋮ Implementation of Code Properties via Transducers ⋮ Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring ⋮ On long words avoiding Zimin patterns ⋮ A Pattern Logic for Automata with Outputs ⋮ Regular Expressions and Transducers Over Alphabet-Invariant and User-Defined Labels
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sur une variante des fonctions séquentielles
- Single-valued a-transducers
- Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
- A proof of Choffrut's theorem on subsequential functions
- How to decide continuity of rational functions on infinite words
- Determinization of transducers over finite and infinite words.
- Economy of description for single-valued transducers
- A note on finite-valued and finitely ambiguous transducers
This page was built for publication: Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
