Bounded Algol-Like Languages

DOI10.2307/1994067zbMath0142.24803OpenAlexW2089107726MaRDI QIDQ5517673

Seymour Ginsburg, Edwin H. Spanier

Publication date: 1964

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/bb73acfef5c8885574de01e13fde6d7a49d85db8

zbMATH Keywords

mathematical logic

Related Items (only showing first 100 items - show all)

Non-closure under complementation for unambiguous linear grammars ⋮ Synchronization of Parikh automata ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Reversing Unbounded Petri Nets ⋮ Commutative Lambek grammars ⋮ A complete refinement procedure for regular separability of context-free languages ⋮ Eliminating the storage tape in reachability constructions. ⋮ The theory of languages ⋮ Counter machines and counter languages ⋮ Multitape NFA: Weak Synchronization of the Input Heads ⋮ Parikh’s Theorem and Descriptional Complexity ⋮ The synthesis of Petri nets from path-automatic specifications ⋮ Porous invariants ⋮ On the equivalence and containment problems for context-free languages ⋮ Bounded languages described by GF(2)-grammars ⋮ Forward analysis and model checking for trace bounded WSTS ⋮ Single-tape reset machines ⋮ On the equivalence and containment problems for context-free languages ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Unnamed Item ⋮ Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable ⋮ The equivalence problem for deterministic MSO tree transducers is decidable ⋮ On regular trace languages ⋮ On the language of primitive words ⋮ Hierarchies of one-way multihead automata languages ⋮ A note on some languages in uniform \(ACC^ 0\) ⋮ The theory of languages ⋮ A theorem on generalizations of proofs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Recognition of poly-slender context-free languages by trellis automata ⋮ Descriptional complexity of bounded context-free languages ⋮ Expressiveness and static analysis of extended conjunctive regular path queries ⋮ Verification in loosely synchronous queue-connected discrete timed automata. ⋮ Sur les ensembles linéaires ⋮ The commutative closure of a binary slip-language is context-free: A new proof. ⋮ An infinite hierarchy of intersections of context-free languages ⋮ A polynomial algorithm for solving systems of two linear diophantine equations ⋮ Unnamed Item ⋮ 2DST mappings of languages and related problems ⋮ Bounded underapproximations ⋮ Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time ⋮ Extended regular expressions of star degree at most two ⋮ Operational State Complexity and Decidability of Jumping Finite Automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Kernels of Sub-classes of Context-Free Languages ⋮ Unboundedness Problems for Languages of Vector Addition Systems. ⋮ Recursive generation of local adjunct languages ⋮ On the expressiveness of Büchi arithmetic ⋮ Learning pomset automata ⋮ Enumerating Projections of Integer Points in Unbounded Polyhedra ⋮ Bounded Context Switching for Valence Systems ⋮ The submonoid and rational subset membership problems for graph groups. ⋮ Forward Analysis and Model Checking for Trace Bounded WSTS ⋮ Extended regular expressions of arbitrary star degrees ⋮ The ring of \(k\)-regular sequences ⋮ Learning semilinear sets from examples and via queries ⋮ Unnamed Item ⋮ Sparse and slender subsets of monoids. ⋮ Properties of right one-way jumping finite automata ⋮ Sur quelques classes d’applications de $N^2$ dans les ensembles finis ⋮ Observations about bounded languages and developmental systems ⋮ A note on semilinear sets and bounded-reversal multihead pushdown automata ⋮ The decidability of a mapping problem for generalized sequential machines with final states ⋮ The growth function of context-free languages ⋮ On Parikh slender context-free languages ⋮ On the Petri net realization of context-free graphs ⋮ Transductions des langages de Chomsky ⋮ Bounded AFLs ⋮ Rational relations having a rational trace on each finite intersection of rational relations ⋮ First-order logics: some characterizations and closure properties ⋮ A useful device for showing the solvability of some decision problems ⋮ Proving containment of bounded AFL ⋮ Unnamed Item ⋮ Finite automata with multiplication ⋮ Complementation of Branching Automata for Scattered and Countable N-Free Posets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems ⋮ Counting productions in context-free derivations ⋮ Some decision problems concerning sequential transducers and checking automata ⋮ The binomial equivalence classes of finite words ⋮ Non axiomatisability of positive relation algebras with constants, via graph homomorphisms ⋮ Syntactic operators on full semiAFLs ⋮ Rational sets in commutative monoids ⋮ String and graph grammar characterizations of bounded regular languages ⋮ A characterization of semilinear sets ⋮ Substitution and bounded languages ⋮ AFL with the semilinear property ⋮ On lengths of words in context-free languages ⋮ Ambiguity and decision problems for local adjunct languages ⋮ Mutually divisible semigroups ⋮ A characterization of poly-slender context-free languages ⋮ Decidability of Right One-Way Jumping Finite Automata ⋮ Counter machines and verification problems. ⋮ The complexity of the satisfiability problem for Krom formulas ⋮ A note on Parikh maps, abstract languages, and decision problems ⋮ Extended automata-like regular expressions of star degree at most (2,1)

This page was built for publication: Bounded Algol-Like Languages