Decision Problems for Finite Automata over Infinite Algebraic Structures

DOI10.1007/978-3-319-40946-7_1MaRDI QIDQ2830202zbMATH OpenOpenAlexFDO

Authors Bakhadyr Khoussainov, Jiamou Liu

Publication date 9 November 2016

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-40946-7_1

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• Decision Problems of Finite Automata Design and Related Arithmetics
• Decision problems for deterministic pushdown automata on infinite words
• scientific article; zbMATH DE number 459363
• Intractability of decision problems for finite-memory automata
• scientific article; zbMATH DE number 4769
• scientific article; zbMATH DE number 49206
• Automata over infinite alphabets
• scientific article; zbMATH DE number 14392
• Automata on algebraic structures

Cites work

• Algorithmic Analysis of Array-Accessing Programs
• Automata and Logics for Words and Trees over an Infinite Alphabet
• Automata based verification over linearly ordered data domains
• Automated Technology for Verification and Analysis
• Deterministic automata. Simulation, universality and minimality
• Finite automata over structures (extended abstract)
• Finite nondeterministic automata: simulation and minimality
• Finite state machines for strings over infinite alphabets
• Finite-memory automata
• Flat Parametric Counter Automata
• Generalized finite automata over real and complex numbers
• scientific article; zbMATH DE number 5605134 (Why is no real title available?)
• scientific article; zbMATH DE number 42574 (Why is no real title available?)
• scientific article; zbMATH DE number 1956513 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Periodic generalized automata over the reals
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Reversal-Bounded Multicounter Machines and Their Decision Problems

Cited in

(15)

• Intractability of decision problems for finite-memory automata
• Decision problems for subclasses of rational relations over finite and infinite words
• Deciding quantifier-free definability in finite algebraic structures
• Periodic generalized automata over the reals
• Dualizability of automatic algebras.
• A computation model with automatic functions and relations as primitive operations
• Finite automata over structures (extended abstract)
• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 177531 (Why is no real title available?)
• scientific article; zbMATH DE number 459363 (Why is no real title available?)
• scientific article; zbMATH DE number 1497854 (Why is no real title available?)
• DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA
• Generalized finite automata over real and complex numbers
• Fundamentals of Computation Theory
• \(\mathbb {N}\)-memory automata over the alphabet \(\mathbb {N}\)

This page was built for publication: Decision Problems for Finite Automata over Infinite Algebraic Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830202)