scientific article; zbMATH DE number 618821

Publication date: 11 August 1994

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

computational complexity automata theory semigroup theory

Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Categories of machines, automata (18B20)

Related Items

Bilateral locally testable languages., Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, Pointlike sets and separation: a personal perspective, Vectorial languages and linear temporal logic, An extension of the wreath product principle for finite Mazurkiewicz traces, Efficient algorithms for membership in Boolean hierarchies of regular languages, First-order logic and its infinitary quantifier extensions over countable words, Level two of the quantifier alternation hierarchy over infinite words, Tameness of Some Locally Trivial Pseudovarieties, Pointlike sets for varieties determined by groups, Formal language constrained path problems, Upper Bounds on Mixing Time of Finite Markov Chains, On FO 2 Quantifier Alternation over Words, The Boolean Algebra of Piecewise Testable Languages, Counting quantifiers, successor relations, and logarithmic space, The complexity of intersecting finite automata having few final states, The regular languages of wire linear $\mathrm{AC}^0$, Algorithmic uses of the Feferman-Vaught theorem, Solving trace equations using lexicographical normal forms, Nominal monoids, A positive extension of Eilenberg's variety theorem for non-regular languages, Dual VP classes, The half-levels of the $\mathrm {FO}_2$ alternation hierarchy, A Circuit Complexity Approach to Transductions, Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$, Linear circuits, two-variable logic and weakly blocked monoids, EF+EX Forest Algebras, Alternation Hierarchies of First Order Logic with Regular Predicates, Separation logics and modalities: a survey, Unnamed Item, Nondeterministic stack register machines, Characterizing classes of regular languages using prefix codes of bounded synchronization delay, Ultrafilters on words for a fragment of logic, Model-checking hierarchical structures, Language theoretical properties of hairpin formations, On Second-Order Monadic Groupoidal Quantifiers, Unnamed Item, Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic, Deciding FO-definability of regular languages, Aural pattern recognition experiments and the subregular hierarchy, On the locality of arb-invariant first-order formulas with modulo counting quantifiers, Solving word equations modulo partial commutations, Unnamed Item, Past pushdown timed automata and safety verification., John Rhodes and the theory of finite semigroups., Extensional Uniformity for Boolean Circuits, Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size, Well-Quasi Orders and Hierarchy Theory, Hierarchies and reducibilities on regular languages related to modulo counting, Work-sensitive dynamic complexity of formal languages, First-order rewritability of ontology-mediated queries in linear temporal logic, Fine hierarchies and m-reducibilities in theoretical computer science, Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages, Complexity results for prefix grammars, Better complexity bounds for cost register automata, Algebraic recognizability of regular tree languages, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, Learning expressions and programs over monoids, Actions, wreath products of $\mathcal C$-varieties and concatenation product., Characterizing CTL-like logics on finite trees., Unnamed Item, Unnamed Item, Expressive power of existential first-order sentences of Büchi's sequential calculus, First-order expressibility of languages with neutral letters or: The Crane Beach conjecture, First-order logics: some characterizations and closure properties, Some results onC-varieties, Logic and rational languages of words indexed by linear orderings, Characterizing EF and EX tree logics, Games for Temporal Logics on Trees, The algebraic theory of Parikh automata, Pro-aperiodic monoids via saturated models, A topological approach to non-uniform complexity, Learning in varieties of the form $\mathbf {V^{*}LI}$ from positive data, Towards a characterization of order-invariant queries over tame graphs, Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG], Metric Temporal Logic with Counting, A Language-Theoretical Approach to Descriptive Complexity, Regular Languages Definable by Majority Quantifiers with Two Variables, A constant-space sequential model of computation for first-order logic, On Existentially First-Order Definable Languages and Their Relation to NP, Difference hierarchies and duality with an application to formal languages, On the power of built-in relations in certain classes of program schemes, Relational Properties Expressible with One Universal Quantifier Are Testable, Automata on finite trees, Varieties, A proof of the Krohn--Rhodes Decomposition Theorem, Programs over semigroups of dot-depth one, Deciding regular grammar logics with converse through first-order logic, Right and left locally testable languages, Merge Decompositions, Two-sided Krohn–Rhodes, and Aperiodic Pointlikes, Quantifiers on languages and codensity monads, Threshold Circuits for Iterated Matrix Product and Powering, Boolean algebras of regular languages, Star-free sets of words on ordinals, Languages defined with modular counting quantifiers, The many faces of a translation, On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology, Logic over words on denumerable ordinals, Free Burnside Semigroups, Relativizations for the logic-automata connection, Expressive Completeness of Separation Logic with Two Variables and No Separating Conjunction, Dual Space of a Lattice as the Completion of a Pervin Space, On spectra of sentences of monadic second order logic with counting, Locality and Centrality: The Variety ZG, Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words, Spectra and satisfiability for logics with successor and a unary function, Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic, Logic vs topology on regular $\omega $-languages, Substitution Principle and semidirect products, Unnamed Item, Unnamed Item, A constant-space sequential model of computation for first-order logic, Weak cardinality theorems, Circuit complexity of regular languages, Level Two of the Quantifier Alternation Hierarchy over Infinite Words, A lower bound for primality, The descriptive complexity approach to LOGCFL, Unnamed Item, Unnamed Item, The Power of Diversity, Transition Function Complexity of Finite Automata, Unnamed Item, Unnamed Item, Where First-Order and Monadic Second-Order Logic Coincide, Unnamed Item, Unnamed Item, The Quantifier Alternation Hierarchy of Synchronous Relations, Unnamed Item, Lower bounds for modular counting by circuits with modular gates, One quantifier alternation in first-order logic with modular predicates, Better complexity bounds for cost register automata, Cascade Products and Temporal Logics on Finite Trees, First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata