Automaticity. I: Properties of a measure of descriptional complexity

DOI10.1006/jcss.1996.0046zbMath0859.68059OpenAlexW1969367179MaRDI QIDQ1816738

Yuri Breitbart, Jeffrey O. Shallit

Publication date: 13 March 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1996.0046

zbMATH Keywords

incomparabilityautomaticity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata sequences (11B85)

Related Items

Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds., Hartmanis-Stearns Conjecture on Real Time and Transcendence, Generalising automaticity to modal properties of finite structures, Regular Growth Automata: Properties of a Class of Finitely Induced Infinite Machines, STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY, On a conjecture of J. Shallit, Automaticity. II: Descriptional complexity in the unary case, Algorithmic introduction of quantified cuts, Learning finite cover automata from queries, Finite Automata, Palindromes, Powers, and Patterns, Approximate Automata for Omega-Regular Languages, On the existence of regular approximations, Automaticity. IV: Sequences, sets, and diversity, Succinct representations of languages by DFA with different levels of reliability, Finite state complexity, Minimal cover-automata for finite languages, Remarks on Separating Words, The binomial equivalence classes of finite words, Enumerating regular expressions and their languages, Detecting palindromes, patterns and borders in regular languages, Compressibility of Finite Languages by Grammars