Back to Search
Start Over
On Families of Full Trios Containing Counter Machine Languages
- Publication Year :
- 2022
-
Abstract
- We look at nondeterministic finite automata augmented with multiple reversal-bounded counters where, during an accepting computation, the behavior of the counters is specified by some fixed pattern. These patterns can serve as a useful "bridge" to other important automata and grammar models in the theoretical computer science literature, thereby helping in their study. Various pattern behaviors are considered, together with characterizations and comparisons. For example, one such pattern defines exactly the smallest full trio containing all the bounded semilinear languages. Another pattern defines the smallest full trio containing all the bounded context-free languages. The "bridging" to other families is then applied, e.g. to certain Turing machine restrictions, as well as other families. Certain general decidability properties are also studied using this framework.<br />28 pages, 1 figure
- Subjects :
- Counter machine
FOS: Computer and information sciences
Theoretical computer science
General Computer Science
Computer science
Formal Languages and Automata Theory (cs.FL)
Computation
media_common.quotation_subject
Computer Science - Formal Languages and Automata Theory
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Bridging (programming)
Turing machine
symbols.namesake
0202 electrical engineering, electronic engineering, information engineering
Nondeterministic finite automaton
media_common
Grammar
Automaton
Decidability
010201 computation theory & mathematics
Bounded function
F.4.3
symbols
020201 artificial intelligence & image processing
Computer Science::Formal Languages and Automata Theory
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....d7b4837c969a0a6ff65ba8cf3ba39e13